package com.leetcode.dynamic_programming;

import javax.jws.Oneway;
import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/7/20 19:24
 */
public class FindMaxForm_474 {

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            // 记录0,1的数量
            int one = 0, zero = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '0') zero++;
                if (str.charAt(i) == '1') one++;
            }
            // 比较坑的是用了个三层循环
            // 状态记录的是i，j和之前的状态，要注意不是和zero one 的状态
            for (int i = m; i >= zero; i--)
                for (int j = n; j >= one; j--)
                    dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
        }
        return dp[m][n];
    }

    static class Solution {

        static class Node {
            int zero, one;
        }

        public int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m + 1][n + 1];
            // 转换成0-1背包
            // 多重背包拆包
            for (String str : strs) {
                // 多重背包问题，对于每一层外包，都需要进行拆包
                int zero = 0, one = 0;
                for (int j = 0; j < str.length(); j++) {
                    if (str.charAt(j) == '0')
                        zero++;
                    else
                        one++;
                }
                for (int i = n; i >= zero; i--) {
                    for (int j = m; j >= one; j--) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
                    }
                }
            }

            return dp[m][n];
        }

    }

}
